\documentclass[11pt]{article}
\usepackage{graphicx}
\newtheorem{define}{Definition}
%\newcommand{\F}{{\mathbb{F}}}
%\usepackage{psfig}
\usepackage{amsmath,amssymb,amsfonts}
\usepackage{fullpage, color}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}

\input{preamble.tex}

\lecture{14}{Oct 4, 2012}{Elena Grigorescu}{Selvakumaran Vadivelmurugan}


\section{Introduction}

We introduced error-correcting codes and linear codes in the last lecture. In this lecture we will discuss in some more details properties of linear codes and we'll describe classical examples of linear codes. We will also show the Hamming bound, which is a bound that relates the distance, rate, and block length parameters of codes and is tight for the Hamming codes. 


Recall that a $(n,k,d)_{q}$ - code is a code of block length $n$, message length $k$ and distance $d=\Delta(C)$ over an alphabet $\Sigma$ with $|\Sigma|=q$.
A linear codes $[n,k,d]_{q}$ is a subspace of $\F_q^n$ of dimension $k$

\section{Linear codes}

Linear codes can be described explicitly by multiple representations as follows.

\begin{enumerate}

\item Generator matrix representation: 
$ C=\{ c \in \F_q^n| \exists m\in \F_q^k,  c = m\cdot G \} $

\item Parity check matrix representation: $ C= \{ c \vert c \cdot H = 0,   H \in \mathbb{F}^{n\times(n-k)}_{q} \}$

\item Basis representation: Let $v_1, v_2, \ldots, v_k\in \mathbb{F}^{n}_{q} $ be a set of linearly independent vectors in $C$. Then $C=\{ \sum ^{k}_{i=1} \alpha_{i} v_{i} \vert \alpha_{i}\in \mathbb{F}_{q} \text{ and } v_{i}\}$. Notice that these are the vectors $v_i$ could be the rows of a generator matrix $G$ for $C$.


\end{enumerate}


Notice that given a code, the generator matrix is not unique. This is also the case for parity check representation or basis representation.

Recall the following useful fact about linear codes.

\begin{lemma}\label{lem:mind} $ \Delta(C)=\min_{c \in C} wt(c).$
\end{lemma}

Determining the minimum distance of arbitrary codes is NP hard.

Knowledge of the parity check matrix of a particular code is helpful in determining  its minimum distance as we will show next.
 
\begin{proposition}  
Let $C$ be a linear codes. Then $\Delta(C)=d $ is the minimum positive  integer such that its parity check matrix $H$ has $d$ linearly dependent rows.
\end{proposition}

\begin{proof} 
By Lemma \ref{lem:mind} we know that there is a codeword $c\in C$ such that $d=wt(c)$. Therefore $c\cdot H=0$. Let $\{i_1,i_2, \ldots, i_d\}$ be the set of indices s.t. $c_{i_j}\not = 0.$ 


Therefore 
\[ \left( \begin{array}{ccccccccc}
   0 & 0 & c_{i_1} & \ldots & 0 & c_{i_d }& 0\ldots \end{array} \right)H=0\]
  
  which implies that $ \sum^{d}_{i=1} c_{i_j}h_{i_j}=0,$ where $h_i$ denotes the vector representing the $i$th row of $H$.
So there exist $d $ linearly dependent rows of $H$. Note that if $H$ had fewer than $d$ linearly dependent rows then there would exist a codeword of smaller than $d$ weight, a contradiction.

\end{proof}


\subsection{Systematic codes}

\begin{definition}  A $(n, k,d)$ code in which each message is mapped to a codeword whose first $k$ entries form the message itself. So, a linear systematic code is a code whose first entries are the message itself and the remaining $n-k$ entries are parity checks of entries of the message.
Namely, $ m=(m_0,m_1,\ldots, m_k) \rightarrow (m,\sum _{i\epsilon S_{1}}m_{i},\sum _{i\epsilon S_{2}}m_{i},\ldots,\sum _{i\epsilon S_{n-k}}m_{i}),$ where  $S_{i}<\left[ k\right], \forall i.$
\end{definition}


Systematic codes are often used in practical applications.

Recall that we have already seen an example of a systematic code in the last lecture. This was the $[7,4,3]_2$ linear code generated by  
$G =
\begin{bmatrix}
1&0&0&0&0&1&1\\
0&1&0&0&1&0&1\\
0&0&1&0&1&1&0\\
0&0&0&1&1&1&1
\end{bmatrix}_{4 \times 7}$

One can indeed easily check that a code is systematic if it can be generated by a matrix $G=\left[ I_{k\times k}~\vert~ A \right],$ where $I_{k\times k}\in \{0,1\}^{k\times k}$ is the identity matrix. Indeed, note that a message $m=(m_{1}, \ldots, m_{k})$ gets mapped to  
$(m_{1}, \ldots, m_{k})\cdot G =(m_{1}, \ldots, m_{k}, m \cdot A) $


We will next argue handwavely that  any linear code is systematic, meaning  given a generator matrix for a linear code it can be transformed into a new generator matrix of the code of the form mentioned above.
We note that a systematic code is not neccesarily  a linear code.


\begin{proposition}\label{prop1} Given linear code $C$ represented by a generator matrix $G$, $G$ can be transformed into 
$ G^{'}=\left[ I_{k\times k}~\vert~ A \right]$ via row and column operations that preserve the code.
\end{proposition}

Indeed note that the following operations do not change the code: (Let us only focus on binary code now.)
\begin{enumerate}
\item Adding rows (mod 2) could only change the basis of the code.

\item Permuting rows does not change the basis.

\item Permuting columns permutes the names of the coordinates, and results in a code that is essentially equivalent to the initial one. 

\end{enumerate}

One can show that these operations are enough to obtain a matrix whose first block is a $I_{k \times k}$ matrix.

In what follows we'll introduce some common linear codes.

\section{The Hamming Code}

\begin{proposition} $ \forall l$ positive integer,  $ \exists $  an $ \left[ 2^{l}-1, 2^{l}-l-1,3 \right] _{2}$.
\end{proposition}


In words, one can encode messages of length $k=2^{l}-l-1$ into codewords of length $n=2^l-1$ and obtain a code of distance $3$, called the Hamming code. This code was proposed in the famous paper of Hamming, 1950 that introduced the area of coding theory.

\begin{proof}
We define the code by describing its parity check matrix $H$. $H$ is a $n\times (n-k)$ binary matrix where the rows are the vectors representing the binary expansion of the integers in $1, 2, \ldots, n$ (therefore each such representation has length $l$ and there are $  2 ^{l} -1 $ rows.)
\\\\
 Namely,

\[ H = \left( \begin{array}{ccccc}
  0 & 0 & ... & 0 & 1 \\
  0 & 0 & ... & 1 & 0 \\
  \vdots  \\

  1 & 1 & ... & 1 & 1 \end{array} \right)\] 



By Proposition \ref{prop1} the above code has distance $3$. Indeed, it is easy to check that the minimum number of linearly dependent rows is $3$ (the first $3$ rows are linearly dependent and there cannot be fewer linearly dependent rows).

\end{proof}

Therefore we have shown that we can get a code of distance $3$ by appending $\log k$ parity bits to messages of length $k$. Could we have achieved the same distance by appending fewer redundancy bits? The next bound, which was also demonstrated in Hamming's initial paper \cite{HAMMING1950}, shows that this tradeoff is essentially tight.


\subsection{The Hamming Bound}


Let $y\in \{0,1\}^n$ and let $t>0$. Define by $B(y,t)$  a ball of radius $t$ around $y$, i.e. $$B(y,t)=\{x\in \{0,1\}^n | d(x, y)\leq t\}.$$
(All the distances are Hamming distances.)  


\begin{center}
$ \includegraphics[scale=0.5]{fig1.png} $
\end{center}

Define $Vol(B(y,t))=\vert B(y,t)\vert$. Therefore, for any $y$ we have $Vol(B(y,t) =Vol(B(\overline{0},t)).$
% 
%  
% All the balls in the below figure have the same volume.
%  
It is easy to see that the volume of a ball of radius $t$ is \[ Vol(B(\overline{0},t)) = \sum _{i=0}^{t} \left( \begin{array}{c}
 n\\
  i \end{array} \right)\]. 

\begin{theorem}(The Hamming bound)

If $ \left( n,k,d\right) _{2} $ is a code, then

\begin{center}
$ 2^{k} Vol \left( B \left( 0,\left[ \frac{d-1}{2} \right] \right) \right) \leq 2^{n} $
\end{center}

\end{theorem}
\begin{proof}
\begin{center}
$ \includegraphics[scale=0.25]{fig2.png} $
\end{center}
Since $d$ is the minimum distance of the code, if follows that balls of radius $ \left[ \frac{d-1}{2} \right] $ don't intersect.  Since the message length is $k$, there are $2^{k} $ code words.
So if we draw balls of radius $ \left[ \frac{d-1}{2} \right] $ around the codewords in $C$ then $\bigcup_{c\in C}  B\left(c,\left[\frac{d-1}{2}\right ]\right)$  could at most cover all the $2^n$ points in the ambient space and so
$$ 2^k=\left| \bigcup_{c\in C}  B\left( c,\left[\frac{d-1}{2}\right ]\right) \right| \leq 2^{n}.$$

\end{proof}

We now verify that the Hamming bound is tight for the Hamming code.
For $d=3$ $Vol(B(\bar{0},1))=n+1.$ Indeed, plugging in the parameters of the Hamming code we have that
$ 2^{2^{l}-l-1} (2^{l}) = 2^{2^{l}-1}=2^{n}$, and so 
$2^{k}\cdot(n+1)\leq 2^{n}.$

The Hamming bound shown here for the binary alphabet can be easily  generalized to alphabets of size $q$. The volume of a ball of radius $t$ is in this case 
$$ Vol \left( B\left( 0,t\right) \right) =\sum_{i=0}^{t} {{n}\choose{i}} \left( q-1\right) ^{i}.$$

\begin{theorem}(Hamming bound)
If $C$ is a $\left(n,k,d\right)_{q} $ code then 

$$ q^{k} \cdot Vol_{q}\left(\frac{d-1}{2},0 \right)\leq q^{n}.$$

\end{theorem}

\section{The Hadamard code}

We will next define the dual of linear codes.


\begin{definition} The {\em dual} of linear code $C$ is the code
$C^{\perp}=\{ y\vert \langle y,c \rangle=0~~ \forall c \in C\}.$
\end{definition}

Since $C$ is a linear subspace so is its dual. 

\begin{proposition}
$ C^{\bot} $ is also linear code.
\end{proposition}


\begin{proposition}
 $ C^{\bot} $ is generated by $H^{\top}$, where $H$ is the parity check of $C$, and $H^{\top}$ is its transpose.
\end{proposition}

So $C=\{c| cH=0\}$ and $C^{\bot} = \lbrace y \vert \exists z, y=zH^{\top}\rbrace$.



The dual of the Hamming code is called the Hadamard code (actually the Hadamard code is slightly modified by an extra $0$ appended to each codeword).  Therefore the Hadamard code is generated by the matrix


\[ H^{\top} = \left[ \begin{array}{cccccc}
0& 0& 0& 0& \ldots& 1 \\
0& 0& 1& 1& \ldots& 1 \\
  \vdots  \\
0& 1&  1&  1&  \ldots& 1 \end{array} \right]\] 
  
So the columns are the binary representations of all the integers $0, 1, 2, \ldots, 2^k-1$.  

\begin{proposition}
The Hadamard code (denoted Had) is a 
$ \left[n={2^{k}},k,2^{k-1} \right]$ code.
(So its distance is $d = \frac{n}{2}$.)

\end{proposition}
\begin{proof}
We only need to show its distance. Namely, 
we show that $\forall c \in \text{Had}, c \neq 0$, we have $wt(c)=n/2$.
So $c$ can be expressed as
\[  \left( m_{0},m_{1},\ldots,m_{k-1}\right)  \left( \begin{array}{ccccc}
 0 & 0 & ... & 0 & 1 \\
 0 & 0 & ... & 1 & 0 \\
  \vdots  \\

  \underbrace{0}_{\alpha_{0}} & \underbrace{1}_{\alpha_{1}} & ... & 1 & \underbrace{1}_{\alpha_{2^{k}-1}} \end{array} \right).\] 

This implies that  $c= \left( <m,\alpha_{0}>,<m,\alpha_{1}>,\ldots<m,\alpha_{2^{k}-1}>\right).$
We will show how to pair up the set of coordinates into $n/2$ pairs s.t. for any pair $(i, j)$ it is the case that  $c_i\not =c_j$. 

Let $i$ be such that $ m_{i}\neq 0.$
For $\alpha\in \{0,1\}^k$ pair it up with $\alpha+e_{i}$, where $e_i$ is the $i$th fundamental basis vector $ e_{i}=\left( 0 0\ldots0\underbrace{1}_{i}00\right).$
So $$<m,\alpha+e_{i}>=<m,\alpha>+<m,e_{i}>=<m,\alpha>+1,$$ which finishes the proof.
 
\end{proof}

So the Had code has good distance $d=\frac{n}{2}$ (so $\delta(Had)=\frac{1}{2}$),  but it has very bad rate $r=\frac{k}{2^{k}}\rightarrow 0,$ as $k\rightarrow \infty.$

A good code is one where both the rate and the relative distance are constants (as the block length $n\infty$. Next we see a code that can achieve these parameters. 


\section{Reed-Solomon Codes}
The Reed-Solomon code is defined over a large alphabets $q$ \cite{REED1960}.

Given the prime power $q$, and $n\leq q,$ and $k\leq n $, the Reed-Solomon code can be constructed as follows:


\begin{enumerate}

\item  Pick $ \alpha_{1}\ldots\alpha_{n}\in \mathbb{F}_{q}$ (all distinct). (We can do so since $n\leq q$.)


\item  The code maps messages in $\F_q^k$ to mesages in $\F_q^n$.
First, associate to the message $\left( m_0,\ldots m_{k-1} \right) \in \mathbb{F}_{q}^{k}  $
the polynomial
$m(x)=\sum^{k-1}_{i=0} m_{i}x^{i}\in \mathbb{F}_{q}[x]$.
Finally encode the message $\left( m_0,\ldots m_{k-1} \right)$ by $(m(\alpha_1),\ldots, m(\alpha_n)$.

\end{enumerate}
\begin{proposition}
$RS_{q,n,k}$ is a linear code.  
\end{proposition}
\begin{proof}

We need to verify that 
$\forall c_{1},c_{2}\in C $
$c_{1}+c_{2} \in C$
and that  $\forall \alpha \in \mathbb{F}_{q}$ $\alpha c_{1} \in C$

Let $c_{1}=\left( m \left( \alpha_{1} \right), m \left( \alpha_{2} \right) \ldots m \left(\alpha_{n} \right) \right) $
and 
$ c_{2}=\left( p \left( \alpha_{1} \right), p \left( \alpha_{2} \right) \ldots p \left(\alpha_{n} \right) \right) $
Then

$ c_{1}+c_{2}=\left( m\left( \alpha_{1}\right) +p\left( \alpha_{1}\right), \cdots\right)=\left( \left( m+p\right) \left( \alpha_{1}\right),\left( m+p\right) \left( \alpha_{2}\right), \cdots\right)\in RS. $


Also, 
$ \alpha  c_1 = \left( \alpha m\left( \alpha_{1}\right),\alpha m\left( \alpha_{2}\right),\cdots,\alpha{m}\left( \alpha_{n}\right) \right) = \left( \left( \alpha m\right) \left( \alpha_{1}\right) ,\cdots\right) \in  $RS

The above inclusions hold since $(m+p)(x)$ is a polynomial of degree $k-1$ and so is the polynomial $ \alpha c_1$.  


  
\end{proof}

In the next lecture we will show that RS codes have the best possible distance for fixed $n, k$, and we'll introduce the Singleton Bound. 



\bibliographystyle{plain}
\bibliography{biblio}



\end{document}
